目標：
這題主要目的在於練習Two Pointer類型的問題應用。

原題：

Question:
Given an array nums of n integers, are there elements a, b, c in numssuch that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析/解題：
題目要求從陣列中找出所有數組a, b, c，
使得三者相加為0，且不能重覆。

老話一句，請記得問有沒有排序XD~
以暴力法解本題的話，會發現每次取三個做組合，
顯然會得到一個O(N³)的時間複雜度的解。
那麼，嘗試排序看看能得到比較好的解嗎？
我們先拿題目的例子來看看，排序過後為
[-4, -1, -1, 0, 1, 2]
按順序排列會有什麼好處呢？
假設我們先固定最左邊的-4為a(因為要組合，我們可以令a<=b<=c)，
那麼b+c必須等於4，這邊使用一個簡單的技巧，
先將b指定給-1的位置，c指定給2的位置，
兩者相加等於1，表示應該要取更大的值才有機會讓和等於4，
於是我們可以將b的位置向右移一格(這裡是重覆的所以可以跳過)，
再次檢查和目標的大小比較。

那麼很容易可以發現一件事情：
當現在的值比目標值大時，表示應該要取更小的值，
只有將c往左移動才有可能達到。
反之，
當現在的值比目標值小時，表示應該要取更大的值，
只有將b往右移動才有可能達到。
因此，在固定a值的時候，只要將後面的數按照上面的方法，
一次移動一格的掃過一遍，就可以得到這個a值所可以成立的組合。

所以最終我們只要將a從0~len(nums)-3按順序跑過一遍，
將中間符合的組合都放進list中，即可得到答案。

重覆性的部分，只要記得檢查前一個和這一個用的數字是否相同即可避免。

上述的做法，由於使用到兩個指標(指針)，並透過移動它們來達到掃描陣列的目的，我們通常稱這樣的解法為Two Pointer，是蠻常用的技巧。
時間複雜度的部分，排序的一般狀況是O(NlogN)，
而a的長度是O(N)，每次都要掃完其後的長度，掃描部分即為O(N²)，
所以總體的時間複雜度為O(N²)。

Java:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>(); 
        for (int i = 0; i < nums.length-2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int j = i + 1, k = nums.length - 1, target = 0 - nums[i];
                while (j < k) {
                    if (nums[j] + nums[k] == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        while (j < k && nums[j] == nums[j + 1]) j++;
                        while (j < k && nums[k] == nums[k - 1]) k--;
                        j++; k--;
                    } else if (nums[j] + nums[k] < target) ++j;
                    else --k;
               }
            }
        }
        return res;
    }
}

Python:
Python的部分提供了另一個的思路，
這是由 RouRouKerr在討論區所提出的解法，這邊是改成Python3版本。
他的想法是，在固定第一個數v的狀況，那當其中一個數為x，
另一個數只能是-v-x(因為加總要等於0)。
故每次將對應的互補數加入到dict中，
我們只要從頭到尾檢查，即可得到所有的正確組合。
這個想法跟前面Two Sum的解法概念是一樣的。
(對應到Java版本的解法也附在註解處)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))
        return list(res)

'''class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums) - 2):
            if i == 0 or (i > 0 and nums[i] != nums[i-1]):
                j, k, target = i + 1, len(nums) - 1, 0 - nums[i]
                while j < k:
                    if nums[j] + nums[k] == target:
                        res.append([nums[i], nums[j], nums[k]])
                        while j < k and nums[j] == nums[j+1]:
                            j += 1
                        while j < k and nums[k] == nums[k-1]:
                            k -= 1
                        j += 1
                        k -= 1
                    elif nums[j] + nums[k] < target:
                        j += 1
                    else:
                        k -= 1
        return res
'''

面試實際可能會遇到的問題：
「(Python)前面不檢查的話後面你怎麼處理重覆？」(用set)
「假設目標不是0的話？」(方法應該是一樣的)
「(Python)dictionary的部分使用set代替會比較快嗎？」(實測過會變慢XD)
「(Java)如果可以改變input/output的變數形態的話，你會希望改動什麼？」
(改output，因為輸出應該固定會是3元組的組合(長度必然是3)，
那大可以使用List<int[]>，用List<List>其實較不理想)

只要掌握了Two Pointers的概念，很多題目其實可以在排序後輕鬆解決，
但記得注意有些題目可以比O(NlogN)快的話，排序會提高時間複雜度歐！

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0021. Merge Two Sorted Lists (Easy)